package sort.leetcode_912;

public class MergeSort {
    public int[] sortArray(int[] nums) {
        if(nums.length == 1){
            return nums;
        }
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void mergeSort(int[] nums, int lo, int hi){
        if(lo >= hi){
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        merge(nums,lo, mid, hi);
    }
    public void merge(int[] nums, int lo, int mid, int hi){
        int[] helper = new int[hi - lo + 1];
        int left = lo;
        int right = mid + 1;
        for(int i = 0; i < helper.length; i++){
            if(left > mid){
                helper[i] = nums[right++];
            }else if(right > hi){
                helper[i] = nums[left++];
            }else if(nums[left] <= nums[right]){
                helper[i] = nums[left++];
            }else{
                helper[i] = nums[right++];
            }
        }
        for(int i = 0; i < helper.length; i++){
            nums[i + lo] = helper[i];
        }
    }
}
